/**
 * Created by L.jp
 * Description:有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
 *
 * 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
 * 要求：时间复杂度 O(nlogn)，空间复杂度 O(1)
 * User: 86189
 * Date: 2022-07-12
 * Time: 9:18
 */
//快排+二分
public class Solution {
    public int findKth(int[] a, int n, int K) {
        return quickSelect(a,K,0,n-1);
    }
    //找到第k大数
    //对一切数据问题都能适应，即使是海量大数据问题，关键是基准值不能选择最左边或者最右边的值
    //否则快排对已经有序的海量数据会超时
    public static int quickSelect(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
        int left = start;
        int right = end;
        int pivot = nums[(start + end) / 2];
        //这里做降序排序
        while (left <= right) {
            while (left <= right && nums[left] > pivot) {
                left++;
            }
            while (left <= right && nums[right] < pivot) {
                right--;
            }
            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        //每一次排完后，left>right
        //如果第k个数据的下标start+k-1小于等于数组右边界
        if (start + k - 1 <= right) {
            return quickSelect(nums, start, right, k);
        }
        //如果第k个数据的下标start+k-1大于等于数左边界
        if (start + k - 1 >= left) {
            return quickSelect(nums, left, end, k - (left - start));
        }
        return nums[right + 1];
    }
}
